#include <iostream.h>
#include <fstream.h>
#include <time.h>
#include<vector>
using namespace std;
#define maxn 10000001

void docfile(int a[], int &n);
void ghifile(int a[], int n);
void swap(int &a, int &b);
int partition (int arr[], int low, int high);
void quickSort(int arr[], int low, int high);
void bubblesort(int a[], int n);
void insertionsort(int a[], int n);
void shellsort(int arr[],int n);
void pigeonhole(int arr[],int n);
void countingsort(int input[],int n);

int a[maxn],n;
int output[maxn]; // The output will have sorted input array

clock_t start, end;
double cpu_time_used;


int main()
{
	docfile(a,n);
	//printArray(a,n);
	
//Bubblesort
//	cout<<"Bubblesort"<<"\n";
//	start = clock();
//	bubblesort(a,n);
//	end = clock();
//	cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
//	cout<<"Time exec:"<<cpu_time_used<<"\n";

	
//Insertionsort
	cout<<"Insertionsort"<<"\n";
	start = clock();
	insertionsort(a,n);
	end = clock();
	cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
	cout<<"Time exec:"<<cpu_time_used<<"\n";

//Shellsort
//	cout<<"Shellsort"<<"\n";
//	start = clock();
//	shellsort(a,n);
//	end = clock();
//	cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
//	cout<<"Time exec:"<<cpu_time_used<<"\n";	
	
//Quicksort
//	cout<<"Quicksort"<<"\n";
//	start = clock();
//	quickSort(a,0,n-1);
//	end = clock();
//	cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
//	cout<<"Time quicksort:"<<cpu_time_used<<"\n";

//Pigeonhole
//	cout<<"Pigeonhole sort"<<"\n";
//	start = clock();
//	pigeonhole(a,n);
//	end = clock();
//	cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
//	cout<<"Time Pigeonhole:"<<cpu_time_used<<"\n";
	
//Counting sort
//	cout<<"Counting sort"<<"\n";
//	start = clock();
//	countingsort(a,n);
//	end = clock();
//	cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
//	cout<<"Time Counting sort:"<<cpu_time_used<<"\n";

//	ghifile(a,n);
	return 0;
}

void docfile(int a[], int &n)
{
	std::ifstream myfile;
	int element;
	myfile.open("D:\\num2.inp");
	if (myfile.is_open())
  	{
  		myfile >> n;
    	for (int i = 0; i < n; i++)
        {
            myfile >> a[i];
            //cout << a[i] << " ";
        }
    	myfile.close();
  	}
  	else cout << "Unable to open file";
}
void ghifile(int a[],int n)
{
	std::ofstream myfile;
	myfile.open("OUT1.out");
	if (myfile.is_open())
  	{
  		myfile<<n <<"\n";
  		for(int i =0;i<n;i++){
		  	myfile <<a[i]<<" ";
		  }
    	myfile.close();
  	}
  	else cout << "Unable to open file";
}
void swap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;
}
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int left = low;
    int right = high - 1;
    while(true){
        while(left <= right && arr[left] < pivot) left++;
        while(right >= left && arr[right] > pivot) right--;
        if (left >= right) break;
        swap(arr[left], arr[right]);
        left++;
        right--;
    }
    swap(arr[left], arr[high]);
    return left;
}
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi l? ch? s? noi ph?n t? n?y d? d?ng d?ng v? tr?
         v? l? ph?n t? chia m?ng l?m 2 m?ng con tr?i & ph?i */
        int pi = partition(arr, low, high);
 
        // G?i d? quy s?p x?p 2 m?ng con tr?i v? ph?i
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
void bubblesort(int a[], int n){
	for (int i=1;i<n;i++){
		//cout<<"\r"<<i;
		for(int j=n-1;j>=i;j--){
			if(a[j]<a[j-1])
				swap(a[j],a[j-1]);
		}
	}
}
void insertionsort(int a[],int n){
	int x,j;
	for(int i=1;i<n;i++){
		//cout<<"\r"<<i;
		x=a[i];j=i-1;
		while((j>=0) && (a[j]>x)){
			a[j+1] = a[j];
			j--;
		}
	a[j+1]=x;
	}
}
void shellsort(int arr[],int n){
	// Start with a big gap, then reduce the gap 
    for (int gap = n/2; gap > 0; gap /= 2) 
    { 
//    	cout<<"\r"<<gap; 
        // Do a gapped insertion sort for this gap size. 
        // The first gap elements a[0..gap-1] are already in gapped order 
        // keep adding one more element until the entire array is 
        // gap sorted  
        for (int i = gap; i < n; i += 1) 
        {	
            // add a[i] to the elements that have been gap sorted 
            // save a[i] in temp and make a hole at position i 
            int temp = arr[i]; 
  
            // shift earlier gap-sorted elements up until the correct  
            // location for a[i] is found 
            int j;             
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
                arr[j] = arr[j - gap]; 
              
            //  put temp (the original a[i]) in its correct location 
            arr[j] = temp; 
        } 
	}
}
void pigeonhole(int arr[],int n){
    // Find minimum and maximum values in arr[] 
    int min = arr[0], max = arr[0]; 
    for (int i = 1; i < n; i++) { 
        if (arr[i] < min) 
            min = arr[i]; 
        if (arr[i] > max) 
            max = arr[i]; 
    } 
    int range = max - min + 1; // Find range 
  
    // Create an array of vectors. Size of array 
    // range. Each vector represents a hole that 
    // is going to contain matching elements. 
    vector<int> holes[range]; 
  
    // Traverse through input array and put every 
    // element in its respective hole 
    for (int i = 0; i < n; i++) 
        holes[arr[i] - min].push_back(arr[i]); 
  
    // Traverse through all holes one by one. For 
    // every hole, take its elements and put in 
    // array. 
    int index = 0; // index in sorted array 
    for (int i = 0; i < range; i++) { 
        vector<int>::iterator it; 
        for (it = holes[i].begin(); it != holes[i].end(); ++it) 
            arr[index++] = *it; 
    } 
}
void countingsort(int input[],int n){
    int max = input[0];
    int min = input[0];
 
    int i;
    for(i = 1; i < n; i++)
    {
        if(input[i] > max)
            max = input[i]; // Maximum value in array
        else if(input[i] < min)
            min = input[i]; // Minimum value in array
    }
 
    int k = max - min + 1; // Size of count array
 
    int count_array[k]; // Create a count_array to store count of each individual input value
    for(i=0; i<k; i++)
        count_array[i]=0;
 
    for(i = 0; i < n; i++)
        count_array[input[i] - min]++; // Store count of each individual input value
 
    /* Change count_array so that count_array now contains actual
     position of input values in output array */
    for(i = 1; i < k; i++)
        count_array[i] += count_array[i - 1];
 
    // Populate output array using count_array and input array
    for(i = 0; i < n; i++)
    {
        output[count_array[input[i] - min] - 1] = input[i];
        count_array[input[i] - min]--;
    }
 
    for(i = 0; i < n; i++)
        input[i] = output[i]; // Copy the output array to input, so that input now contains sorted values
 
}